package codewars.arrays;

import java.util.stream.IntStream;

/**
 * Number of trailing zeros of N!
 * CodeWars: https://www.codewars.com/kata/number-of-trailing-zeros-of-n/train/java
 * Topics: Topics: algorithms, mathematics, numbers
 *
 * 给一个数字 n
 * 求 n的阶乘的结果，在最末尾的0的个数
 * 举栗：
 * n=6 则返回 1。因为6!=720
 *
 * 注意：
 * 1000! 有2568位，所以考虑不要用常规思路求阶乘结果来计算末尾0的长度
 *
 * 参考答案：https://www.cnblogs.com/kuliuheng/p/4102917.html
 *
 * Created by yzy on 2019-05-11 23:14
 */
public class NumberOfTrailingZerosOfNFactorial {

    public static void main(String[] args) {
        int n = 1000;
//        System.out.println(zeros_optimize_timeout(n));
//        System.out.println(zeros_optimize_v2(n));
//        System.out.println(zeros_optimize_v3(n));
        System.out.println(zeros_optimize_v4(n));
    }

    /**
     * 最优解的递归写法
     * @param n
     * @return
     */
    public static int zeros_recursion(int n) {
        if(n/5 == 0)
            return 0;
        return n/5 + zeros_recursion(n/5);
    }

    /**
     * 【最优解】
     * 找n个数里，有多少个5的整数倍，也就是 n/5
     * 那么在得到的数里，又有多少个5的整数倍，还是 n/5
     * 一直这样递归，直到 n<5
     * @param n
     * @return
     */
    public static int zeros_optimize_v4(int n){
        int count = 0;
        while(n>=5){
            n = n/5;
            count +=n;
        }
        return count;
    }



    /**
     * 思路：数前n个数整除5之后，有多少个5
     * （因为2的倍数肯定比5多，找5就一定能找到对应2的倍数来凑10）
     *
     * 还是会超时，推测是因为取余操作耗时
     * @param n
     * @return
     */
    public static int zeros_optimize_v3(int n){
        int count = 0;
        int tmp;
        for(int i=5; i<=n; i+=5){
            tmp=i;
            while(tmp%5==0){
                count++;
                tmp = tmp/5;
            }
        }
        return count;
    }

    /**
     * 对之前的再优化
     * 思路：
     * 必须得有 一个2和一个5，两个相乘才能得到一个10，也就是末尾得到一个0
     * 遍历1~n，如果遇到2或者5的倍数，就整除，然后对2 或者 5的Num++;
     * 最后求两个数字中，小的那个，就是最终结果0的个数。
     *
     * 【缺陷】：
     * 求余操作耗费性能
     *
     * @param n
     * @return
     */
    public static int zeros_optimize_v2(int n){
        int twoNum = 0;
        int fiveNum = 0;
        int tmp;
        for(int i=1; i<=n; i++){
            tmp = i;
            while(tmp>=2 && tmp%2 == 0){
                tmp = tmp/2;
                twoNum++;
            }
            while(tmp>=5 && tmp%5 == 0){
                tmp = tmp/5;
                fiveNum++;
            }
        }
        return Math.min(twoNum, fiveNum);
    }


    /**
     * 对zeros_error的优化
     * 思路：
     * 只有 2的整数倍 和 5的整数倍 相乘，才会得到末尾的0
     *
     *
     *
     * @param n
     * @return
     */
    public static int zeros_optimize_timeout(int n){
        long startTime = System.currentTimeMillis();
        int zeroCount = 0;
        long tmp = 1;
        for(int i=1; i<=n; i++){
            if(i%2 !=0 && i%5 != 0){
                continue;
            }
            tmp *=i;
            while(tmp % 10 == 0){
                tmp /=10;
                zeroCount++;
            }
        }
        long endTime = System.currentTimeMillis();
        System.out.println("zeros_optimize Cost " + (endTime-startTime) + " ms");
        return zeroCount;
    }

    /**
     * 思路：
     * 如果末尾有0则除10去0并count+1，一直到结束
     *
     * 【这个算法是错误的】
     * n较小时结果正确。
     * 但是，n较大时，tmp的值会超出long能够存储的范围，导致结果是错的
     *
     * @param n
     * @return
     */
    public static int zeros_error(int n) {
        long startTime = System.currentTimeMillis();
        int zeroCount = 0;
        long tmp = 1;
        for(int i=1; i<=n; i++){
            tmp *=i;
            while(tmp % 10 == 0){
                tmp /=10;
                zeroCount++;
            }
        }
        long endTime = System.currentTimeMillis();
        System.out.println("zeros_optimize Cost " + (endTime-startTime) + " ms");
        return zeroCount;
    }
}
